/*
https://leetcode-cn.com/problems/majority-element-ii/solution/qiu-zhong-shu-ii-by-leetcode-solution-y1rn/
 */
import java.util.ArrayList;
import java.util.List;

public class Solution229 {
    public List<Integer> majorityElement(int[] nums) {
        int n1=0,v1=0,n2=0,v2=0;
        List<Integer> list=new ArrayList<>();
        for (int num : nums) {
            if (v1>0&&num==n1){
                v1++;
            }else if (v2>0&&num==n2){
                v2++;
            }else if (v1==0){
                n1=num;
                v1=1;
            }else if (v2==0){
                n2=num;
                v2=1;
            }else {
                v1--;v2--;
            }
        }
        int t1=0,t2=0;
        for (int num : nums) {
            if (num == n1) {
                t1++;
            }
            if (num == n2) {
                t2++;
            }
        }
        if (v1!=0 && t1>nums.length/3){
            list.add(n1);
        }
        if (v2!=0 && t2>nums.length/3){
            list.add(n2);
        }
        return list;
    }

    public static void main(String[] args) {
        System.out.println(new Solution229().majorityElement(new int[]{1,1,1,3,3,2,2,2}));
    }
}
